1206. f91

МакКарти – известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию f91, которая определена для всякого натурального числа n следующим образом:

Если n ≤ 100, то f91(n) = f91(f91(n + 11));

Если n ≥ 101, то f91(n) = n – 10.

Вход. Натуральное число n, не большее 1000000.

Выход. Значение f91(n).

Пример входа	Пример выхода
500	490

РЕШЕНИЕ

рекуррентное соотношение

Анализ алгоритма

Необходимо вычислить значения функции f91(n) для n £ 100.

Имеем: f91(100) = f91(f91(111)) = f91(101) = 91, f91(99) = f91(f91(110)) = f91(100) = 91. Аналогично продолжая, можно заметить что f91(n) = 91, где 1 £ n £ 100.

Таким образом, имеет место соотношение:

f91(n) =

Реализация алгоритма

Выводим результат согласно приведенному выше соотношению.

scanf("%d",&n);

if (n >= 101) res = n - 10; else res = 91;

printf("%d\n",res);